This invention relates to checksum generation.
Checksum generation is useful, for example, in communication among processors interconnected in a network. In a typical network, a packet of information containing, for example, a binary-encoded bit string of control information and data, may be transmitted from an originating processor to a destination processor directly, or through one or more intermediate processors. During transmission, errors may be introduced into the information packet by, for example, spurious network noise. Processing of an erroneous packet by an intermediate or destination processor may cause that processor to reject, or "lose", the packet, and may also cause the processor to fail.
To guard against such lost packets and failures, error-checking mechanisms may be used to verify the correctness of bits received at a processor, allowing erroneous information packets to be discarded before causing faulty processing to occur. A checking mechanism could involve, for example, generating an arithmetic quantity based on some of the bits to be sent from an originating processor, including the arithmetic quantity in the packet when the packet is transmitted, and then verifying the quantity when the packet is received by an intermediate or destination processor.
One such error-checking mechanism is a so-called arithmetic checksum, defined by the International Organization for Standardization (ISO) in ISO/TC 97/SC 6-ISO 8473: "Information Processing Systems--Data Communications--Protocol for Providing the Connectionless-mode Network Service", with its Addendum 1: "Provision of the Underlying Service assumed by the ISO 8473," March, 1987, incorporated herein by reference. The ISO checksum is required as part of the standard communications protocol for any network subscribing to the ISO network configuration.
Referring to FIG. 1A, the ISO protocol for error-checking an information packet is based on grouping bits of the packet into eight-bit groups, or octets. The eight bit positions in an octet are numbered 1 through 8 from right to left. The value of a given bit that appears as a "1" is then taken to be 2.sup.p-1, where p is the bit position. For example, 2.degree. (=1) is the value for the first (least significant) bit position, and 2.sup.7 (=128) is the value for the eighth (most significant) bit position. An octet is then taken to have a so-called octet value that is equal to the sum of the bit position values of "1" bits. As shown in FIG. 1B, an octet having, for example, the bits 10110101 is said to have an octet value of 181 base 10.
Following the ISO network protocol, a checksum is generated with regard to an information packet whenever that packet is transmitted or received. The checksum may be generated using all of the bits in the packet, or alternatively, only a segment of the packet's bits. In either case, the string of bits that is used in the checksum generation is called the checksum scope. As shown in FIG. 1C, the checksum scope is specified to include some number, L, of octets. These L octets are numbered from 1 to L, with octet 1 [L] being that octet in the checksum scope which is first [last] submitted to the network during an information packet transmittal.
When a processor, e.g., an originating or destination processor, in an ISO network generates a checksum for an information packet's checksum scope, the processor processes, in sequence, the L octets of the checksum scope bit string to produce a checksum value. This generation technique follows a checksum algorithm as defined by J. G. Fletcher in "An Arithmetic Checksum for Serial Transmission," IEEE Trans. Comm., Vol. Com30, No. 1, 1982.
Referring to FIG. 1D, the i.sup.th octet in a checksum scope is assembled by a processor from eight contiguous bits in the bit string. The processor then assigns the bit position values of 2.sup.0, 2.sup.q, 2.sup.2, 2.sup.3, 2.sup.4, 2.sup.5, 2.sup.6, and 2.sup.7 to the corresponding bits in the octet, starting from the right-most (least significant) bit, respectively. With this bit position assignment, the octet is given an octet value O.sub.i that is the sum of the bit position values assigned to all of the octet bits which are a "1", giving an octet value O.sub.i equal to 181 base 10 for the example sequence.
The octet values O.sub.i (i=1 to L) in a checksum scope, are used by a processor to generate a checksum, each octet value being used as soon as it is generated. The checksum comprises two checksum variables, C.sub.0 and C.sub.1, which are each a function of the checksum scope's octet values. When a processor begins evaluation of a checksum scope, both variables C.sub.0 and C.sub.1 are set equal to zero, and then iteratively updated as each octet value O.sub.i in the checksum scope is determined, as follows: ##EQU1## where "mod 255" indicates modulo arithmetic base 255. Using this iterative process, once the L octets in the checksum scope have been evaluated, C.sub.0 (i=L) is equal to the arithmetic sum, mod 255, of the octet values in the checksum scope, and C.sub.1 (i=L) is equal to the weighted arithmetic sum, mod 255, of the octet values in the checksum scope, i.e., the sum of (1.times.O.sub.L)+(2.times.O.sub.L-1)+ . . . +(L.times.O.sub.1), mod 255.
Thus, referring to FIG. 2A, a pictorial representation of the arithmetic sum comprising the final value of C.sub.0 (i=L) includes one octet value block for each octet in the checksum scope. Similarly, a pictorial representation of the weighted arithmetic sum comprising the final value of C.sub.1 (i=L), as shown in FIG. 2B, includes one octet value block for the last octet in the checksum scope, and an increasing number of octet value blocks for each of the preceding octets, with the first octet contributing L octet value blocks to the value of C.sub.1 (i=L).
A processor "builds" this stair-cased triangular representation for the value of C.sub.1 (i=L), as well as the rectangular representation for the value of C.sub.0 (i=L), using the iterative relationship discussed above; each iteration of the relationship adds a number of octet value blocks to the triangle and rectangle in the following way. Referring to FIG. 2C, after a processor executes the iterative relationship once, both C.sub.1 and C.sub.0 include one block for the first octet's value, O.sub.1.A second execution of the relationship adds one block to C.sub.0 for the second octet's value, as shown in FIG. 2D, and to C.sub.1 adds one additional block for the first octet's value and one block for the second octet's value, O.sub.2. Similarly, a third execution of the relationship adds, as shown in FIG. 2E, one block to C.sub.0 for the third octet's value, and to C.sub.1 adds a third block for the first octet's value, a second octet for the second octet's value, and one block for the third octet's value, O.sub. 3.
After executing the iterative process a number, L, of times, the processor has "built" the C.sub.0 (i=L) rectangle to include L octet value blocks, and has "built" the C.sub.1 (i=L) triangle to include L octet value blocks for the first octet and a corresponding number of blocks for the other octets, with the Lth octet contributing one block. If, for example, there are L=9 octets in the checksum scope, then, as shown in FIG. 2F, the C.sub.1 (i-9) stair-cased triangle is 9 blocks long and 9 blocks deep, and the C.sub.0 (i=9) rectangle is 9 blocks long.
Before transmitting an information packet for which a checksum has been generated, an originating processor in an ISO network may further process the packet to reflect the values of the checksum variables C.sub.0 (i=L) and C.sub.1 (i=L). For example, additional octets may be appended to the checksum scope so that recalculation of the two checksum variables C.sub.0 (i=L) and C.sub.1 (i=L) for the new checksum scope would produce a value of zero for both variables.
When an intermediate or destination processor in an ISO network receives an information packet for which a checksum has been generated, it regenerates a checksum for the information packet's checksum scope to verify the correctness of the packet. Each of the octets in the checksum scope is evaluated, in sequence, by the processor to generate values for the checksum variables C.sub.0 (i=L) and C.sub.1 (i=L) with the relationships given above. If, after processing every octet in the checksum scope, the final values of both checksum variables C.sub.0 (i=L) and C.sub.1 (i=L) are equal to zero, the processor is assured with a high probability that it has received a correct information packet. Any nonzero final value for one or both of the regenerated checksum variables indicates that the received information packet is erroneous and therefore should not be processed.